import java.util.*;

public class Solution207 {

    private boolean haveCircle(List<Integer>[] relyArr, Integer tmpLoc, BitSet pathSet, BitSet visitSet){
        if(visitSet.get(tmpLoc)){
            return false;
        }
        if(pathSet.get(tmpLoc)){
            return true;
        }
        visitSet.set(tmpLoc, true);
        List<Integer> tmpRelyList = relyArr[tmpLoc];
        if(tmpRelyList != null){
            pathSet.set(tmpLoc, true);
            for (Integer other : tmpRelyList) {
                if(haveCircle(relyArr, other, pathSet, visitSet)){
                    return true;
                }
            }
            pathSet.set(tmpLoc, false);
        }
        return false;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] relyArr = new List[numCourses];
        for (int[] rely : prerequisites) {
            List<Integer> others = relyArr[rely[0]];
            if(others == null){
                others = new ArrayList<>();
            }
            others.add(rely[1]);
            relyArr[rely[0]] = others;
        }


        BitSet pathSet = new BitSet(numCourses);
        BitSet visitSet = new BitSet(numCourses);
        for (int i = 0; i < numCourses; i++) {
            boolean haveCircle = haveCircle(relyArr, i, pathSet, visitSet);
            if(haveCircle){
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {

        Solution207 s = new Solution207();
        System.out.println(s.canFinish(2, new int[][]{{0, 1}, {1,0}}));
    }
}
